package 栈;

import java.util.HashMap;
import java.util.Stack;

/**
 * @author 陈艺博
 * @date 2021-02-20 20:34
 * @description https://leetcode-cn.com/problems/valid-parentheses/
 * 1. 遇见左字符， 将左字符入栈
 * 2. 遇见右字符
 * - 如果栈是空的， 说明**括号无效**
 * - 如果栈不为空， 将栈顶字符出栈
 * - 如果左右字符不匹配， 说明**括号无效**
 * - 如果左右自然福匹配，继续扫描下一个字符
 * 3. 所有字符扫描完毕后
 * - 栈为空，说明括号有效
 * - 栈不为空，说明**括号无效**
 **/
public class _20_valid_parentheses_有效的括号 {

    /**
     * 无使用容器。 取巧方法，性能较差，不通用
     * 通过查询字符串包含的指定字符，并且替换指定字符，从而得出是否成对出现
     *
     * @param s
     * @return
     */
    public boolean isValidString(String s) {
        while (s.contains("()") || s.contains("{}") || s.contains("[]")) {
            s = s.replace("()", "");
            s = s.replace("{}", "");
            s = s.replace("[]", "");
        }
        return s.isEmpty();
    }

    /**
     * 使用栈作为容器， 进行优化
     *
     * @param s
     * @return
     */
    public boolean isValidStack(String s) {
        Stack<Character> stack = new Stack<>();
        int len = s.length();
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '{' || c == '[') {//如果是左括号入栈
                stack.push(c);
            } else {
                if (stack.isEmpty()) {//没有左括号
                    return false;
                }
                char left = stack.pop();
                if (left == '(' && c != ')') {
                    return false;
                }
                if (left == '{' && c != '}') {
                    return false;
                }
                if (left == '[' && c != ']') {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

    /**
     * 使用HasMap字典表方法解决问题
     */
    private static HashMap<Character, Character> map = new HashMap<>();

    static {
        map.put('(', ')');
        map.put('[', ']');
        map.put('{', '}');
    }

    static public boolean isValidMap(String s) {
        Stack<Character> stack = new Stack<>();
        int len = s.length();
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)) {// 获取左括号， 通过判断c是否在map的key中
                stack.push(c);
            } else {
                if (stack.isEmpty()) {
                    return false; // 没有左括号
                }
                if (c != map.get(stack.pop())) {// 获取并删除栈顶元素，将栈顶作为key查询map中对应的元素
                    return false;// 判断是否是 栈中左括号对应的右括号
                }
            }
        }
        return stack.isEmpty();// 栈顶没有元素，并且都是成对出现
    }
    /**
     * ----------------------性能测试-------------------------------------------
     * 方法              运行时间    消耗内存
     * isValidString    45 ms   	39.1 MB
     * isValidStack     1 ms    	36.6 MB
     * isValidMap       2 ms        36.6 MB
     */
}

